#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        
        //时间复杂度可能会有点高
        sort(nums.begin(),nums.end());
        vector<vector<int>> dp(nums.size(),vector<int>{});
        int index = 0;
        dp[0] = (vector<int>{nums[0]});
        for(int i = 1;i<nums.size();++i){
            int status = 1;
            for(int j = i-1;j>=0;--j){
                if(nums[i]%nums[j]==0&&dp[j].size()>=dp[i].size()){
                    dp[i] = dp[j];
                    dp[i].push_back(nums[i]);
                    index = (dp[index].size()>=dp[i].size())?index:i;
                    status =0;
                }
            }
            if(status){
                dp[i].push_back(nums[i]);
            }


        }
        return dp[index];
    }
};

int main(){
    vector<int> nums = {1,2,3,4};
    Solution S;
    vector<int> result = S.largestDivisibleSubset(nums);
    return 0;
}